#include<stdio.h>

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

//向下调整算法
void AdjustDown(int* parr, int n, int root)
{
  int parent = root;
  int child = parent * 2 + 1;

  while(child < n)
  {
    //选出较大的子节点
    if(child + 1 < n && parr[child + 1] > parr[child])
    {
      child += 1;
    }

    if(parr[child] > parr[parent])
    {
      Swap(&parr[child], &parr[parent]);
      parent = child;
      child = parent * 2 + 1;
    } 
    else
    {
      break;
    }
  }
}

void HeapSort(int* parr, int n)
{
  //建堆
  int i = 0;
  for(i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(parr, n, i);
  }

  //选择和排序
  int end = n - 1;
  while(end > 0)
  {
    Swap(&parr[0], &parr[end]);
    AdjustDown(parr, end, 0);
    end--;
  }
}

void PrintArr(int* parr, int n)
{
  int i = 0;
  for(i = 0; i < n; i++)
  {
    printf("%d ", parr[i]);
  }
}

void test1(void)
{
  int arr[] = { 1, 3, 5, 7, 2, 4, 6, 8  };
  int sz = sizeof(arr)/sizeof(arr[0]);
  HeapSort(arr, sz);
  PrintArr(arr, sz);
}

void SelectSort(int* parr, int n)
{
  int begin = 0;
  int end = n - 1;
  while(begin < end)
  {
    int i = 0;
    int mini = begin;
    int maxi = begin;
    for(i = begin; i <= end; i++)
    {
      if(parr[i] < parr[mini])
      {
        mini = i;
      }
      if(parr[i] > parr[maxi])
      {
        maxi = i;
      }
    }
    Swap(&parr[begin], &parr[mini]);
    //修正maxi
    //如果不想进行修正操作，可以先进行最大值交换，再进行最小值交换
    if(begin == maxi)
    {
      maxi = mini;
    }
    Swap(&parr[end], &parr[maxi]);
    begin++;
    end--;
  }
}

void test2(void)
{
  int arr[] = { 1, 3, 5, 7, 2, 4, 6, 8  };
  int sz = sizeof(arr)/sizeof(arr[0]);
  SelectSort(arr, sz);
  PrintArr(arr, sz);
}

int main()
{
  //test1();
  test2();
  return 0;
}
